home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.sources.misc
- From: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
- Subject: v06i043: lookup -- look up commands in table
- Keywords: c++, lookup table, linear and binary search
- Reply-To: geac!rae (Reid Ellis)
- Organization: T'nir Software
-
- Posting-number: Volume 6, Issue 43
- Submitted-by: rae@b.UUCP (Reid Ellis)
- Archive-name: lookup.c++
-
-
- The following shar implements a lookup table in C++. Two alternate
- algorithms are presented, binary and linear search, in the files lookup.c
- and lookup2.c, respectively. See the README file for more details. Don't
- worry -- there's an "exit" before my .signature.
-
- Reid
-
- #! /bin/sh
- # This is a shell archive. Remove anything before this line, then unpack
- # it by saving it into a file and typing "sh file". To overwrite existing
- # files, type "sh file -c". You can also feed this as standard input via
- # unshar, or by typing "sh <file", e.g.. If this archive is complete, you
- # will see the following message at the end:
- # "End of shell archive."
- # Contents: Makefile README lookup.c lookup.h lookup2.c test.c
- # testcmd.c testhelp.c
- # Wrapped by rae@geaclib on Tue Feb 7 05:37:45 1989
- PATH=/bin:/usr/bin:/usr/ucb ; export PATH
- if test -f Makefile -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"Makefile\"
- else
- echo shar: Extracting \"Makefile\" \(419 characters\)
- sed "s/^X//" >Makefile <<'END_OF_Makefile'
- XCC = CC -c -I/usr/include/CC
- XLD = CC
- X
- X.c.o:
- X $(CC) $(CFLAGS) $<
- X
- X# lookup2 does a linear search -- good for unsorted table
- X# lookup does a binary search -- good for a sorted table
- XOBJ = test.o lookup2.o testcmd.o testhelp.o
- X#OBJ = test.o lookup.o testcmd.o testhelp.o
- XTARG = tt
- X
- X$(TARG): $(OBJ)
- X $(LD) -o $(TARG) $(OBJ) $(LDFLAGS)
- X @strip $(TARG)
- X
- Xlookup.o lookup2.o : lookup.h
- Xtest.o : lookup.h
- Xtesthelp.o : lookup.h
- END_OF_Makefile
- if test 419 -ne `wc -c <Makefile`; then
- echo shar: \"Makefile\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f README -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"README\"
- else
- echo shar: Extracting \"README\" \(2827 characters\)
- sed "s/^X//" >README <<'END_OF_README'
- XDESCRIPTION
- X
- XUsing the files lookup.c [or lookup2.c] and lookup.h, you can easily maintain
- Xa command lookup table. The table must be of type "entry *", and you can see
- Xin the example code [test.c, testcmd.c, testhelp.c] that I used an aggreagate
- Xarray of the form:
- X
- Xentry list[] = { ... };
- X
- XThe first "entry" in the list must have a count and a pointer to an error
- Xfunction. If you have no error function, create a null function, which
- Xdoes nothing, and use a pointer to it. Since the number occupies the
- Xposition of a char*, you have to cast it to such. i.e., if you have
- X#define'd NUM to the number of elements, you would say
- X
- Xentry list[] = {
- X (char *)NUM, &err,
- X ...
- X };
- X
- Xwhere err is the error-handling function. err would be called when a string
- Xnot in the list is referenced.
- X
- XNow, the list is not the object that does the work. Another object, of class
- X"lookup" is initialized with a pointer to an "entry *". e.g., given the
- Xabove example, you could say:
- X
- Xlookup cmd(list);
- X
- XThereafter, to retrieve the function pointer desired, you simply reference
- X"cmd" with a string:
- X
- Xint (*proc)(const char *);
- Xproc=cmd["query"];
- X
- XThis would cause "proc" to point to the function associated with the
- Xword "query", if any; otherwise, it would point to the error function,
- Xwhich we designated above to be "err". Now you can happily dereference the
- Xpointer and pass it a "const char *":
- X
- Xproc("testing");
- X
- XNow note that you can do both of these at once:
- X
- Xcmd["query"]("Testing");
- X
- XIsn't that special?
- X
- XThe only difference between lookup.c and lookup2.c is the implementation.
- XEach gives you an advantage. If your list of names is sorted, use
- Xlookup.c since it uses a binary search. Obviously, if they are not
- Xin any order, a binary search will not work, so lookup2.c just does
- Xa linear search. This is the only difference between the two.
- X
- X
- XARGUMENT TYPE
- X
- XAll of the function pointers in the "entry" list must take the same
- Xargument[s], if any, and return the same value type. I haven't built
- Xany elegant macros, but there are #defines in "lookup.h" to handle both
- Xof these problems in a less than elegant manner.
- X
- XThe two macros ARG_TYPE and RET_TYPE define the argument type and value
- Xvalue returned by the function pointers. Just change these to handle whatever
- Xtypes you like.
- X
- X
- XCAVEATS
- X
- XThis is one of my first attempts at C++; I hope you find it useful. If
- Xyou make any major modifications, or even more importantly, if you find any
- Xbugs, please let me know so I can fix my source and post the patches for
- Xone and all.
- X
- X
- XCOPYRIGHT
- X
- XI the author hereby place this code in the public domain. Make enough
- Xmoney to buy Canada and hire me as Prime Minister!
- X
- X
- XAUTHOR
- X
- XReid Ellis
- X176 Brookbanks Drive
- XDon Mills, Ontario
- XM3A 2T5
- XCANADA
- X+1 416 446 1644
- Xrae@geaclib.uucp if you're lucky, or else geaclib!rae@geac.uucp
- END_OF_README
- if test 2827 -ne `wc -c <README`; then
- echo shar: \"README\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f lookup.c -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"lookup.c\"
- else
- echo shar: Extracting \"lookup.c\" \(652 characters\)
- sed "s/^X//" >lookup.c <<'END_OF_lookup.c'
- X#include <stream.h>
- X#include <string.h>
- X#include "lookup.h"
- X
- Xproc lookup::operator[](const char *str)
- X {
- X int n;
- X entry
- X *upper = table + max - 1,
- X *lower = table,
- X *mid = lower + (upper-lower)/2;
- X
- X for(n=1; n && upper - lower > 1; )
- X {
- X n = strcmp(str, mid->name);
- X if(n == 0)
- X upper = lower = mid;
- X else
- X {
- X if(n < 0) upper = mid;
- X else lower = mid;
- X mid = lower + (upper - lower)/2;
- X }
- X }
- X
- X if(n < 0) n = strcmp(str, mid->name);
- X else if(n > 0)
- X {
- X mid = upper;
- X n = strcmp(str, mid->name);
- X }
- X
- X if(n) return dflt; // not in table
- X else return mid->f; // found it
- X }
- END_OF_lookup.c
- if test 652 -ne `wc -c <lookup.c`; then
- echo shar: \"lookup.c\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f lookup.h -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"lookup.h\"
- else
- echo shar: Extracting \"lookup.h\" \(392 characters\)
- sed "s/^X//" >lookup.h <<'END_OF_lookup.h'
- X#ifndef LOOKUPH
- X#define LOOKUPH
- X
- X#define ARG_TYPE const char *
- X#define RET_TYPE int
- X
- Xtypedef RET_TYPE (*proc)(ARG_TYPE);
- X
- Xstruct entry {
- X const char *name;
- X proc f;
- X };
- X
- Xclass lookup {
- X entry *table;
- X proc dflt;
- X int max;
- Xpublic:
- X lookup(entry *t) {
- X dflt = t->f;
- X max = int(t->name);
- X table = t + 1;
- X }
- X // This really does take a const char *
- X proc operator[](const char *);
- X };
- X#endif
- END_OF_lookup.h
- if test 392 -ne `wc -c <lookup.h`; then
- echo shar: \"lookup.h\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f lookup2.c -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"lookup2.c\"
- else
- echo shar: Extracting \"lookup2.c\" \(263 characters\)
- sed "s/^X//" >lookup2.c <<'END_OF_lookup2.c'
- X#include <stream.h>
- X#include <string.h>
- X#include "lookup.h"
- X
- Xproc lookup::operator[](const char *str)
- X {
- X entry *t=table;
- X
- X for(; t-table < max; t++)
- X if(!strcmp(t->name, str))
- X break;
- X
- X if(t-table<max) return t->f;
- X else return dflt;
- X }
- END_OF_lookup2.c
- if test 263 -ne `wc -c <lookup2.c`; then
- echo shar: \"lookup2.c\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f test.c -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"test.c\"
- else
- echo shar: Extracting \"test.c\" \(882 characters\)
- sed "s/^X//" >test.c <<'END_OF_test.c'
- X#include <stream.h>
- X#include <string.h>
- X#include "lookup.h"
- X
- Xextern RET_TYPE
- X a(ARG_TYPE),
- X b(ARG_TYPE),
- X c(ARG_TYPE),
- X help(ARG_TYPE),
- X oops(ARG_TYPE);
- X
- Xentry list[] = {
- X (char *)4, &oops,
- X "acmd", &a,
- X "bcmd", &b,
- X "c", &c,
- X "help", &help,
- X };
- X
- Xint main(int argc, char *argv[])
- X {
- X char *progname = argv[0];
- X lookup command(list);
- X char word[200]; // of type ARG_TYPE
- X int i;
- X
- X argc--; // to shut up CC
- X
- X while(cout << "% ", cin >> word && strcmp(word, "quit"))
- X {
- X
- X // Note that in the next statement, we are in
- X // fact saying command[const char *](ARG_TYPE)
- X // In this case, ARG_TYPE *is* const char *, so we
- X // are just passing the same thing to both [] and ().
- X
- X if(i = command[word](word))
- X {
- X // the function returned a non-zero result
- X cerr << form("%s: %s returned %d\n", progname, word, i);
- X }
- X }
- X return 0;
- X }
- END_OF_test.c
- if test 882 -ne `wc -c <test.c`; then
- echo shar: \"test.c\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f testcmd.c -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"testcmd.c\"
- else
- echo shar: Extracting \"testcmd.c\" \(328 characters\)
- sed "s/^X//" >testcmd.c <<'END_OF_testcmd.c'
- X#include <stream.h>
- X
- Xint a(const char *s)
- X {
- X cout << form("a: %s\n", s);
- X return 0;
- X }
- X
- Xint b(const char *s)
- X {
- X cout << form("b: %s\n", s);
- X return 0;
- X }
- X
- Xint c(const char *s)
- X {
- X cout << form("c: %s\n", s);
- X return 0;
- X }
- X
- Xint oops(const char *s)
- X {
- X cout << form("command %s unavailable\n", s);
- X return 0;
- X }
- END_OF_testcmd.c
- if test 328 -ne `wc -c <testcmd.c`; then
- echo shar: \"testcmd.c\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- if test -f testhelp.c -a "${1}" != "-c" ; then
- echo shar: Will not over-write existing file \"testhelp.c\"
- else
- echo shar: Extracting \"testhelp.c\" \(341 characters\)
- sed "s/^X//" >testhelp.c <<'END_OF_testhelp.c'
- X#include <stream.h>
- X#include "lookup.h"
- X
- Xextern entry list[];
- X
- Xint help(const char *s)
- X {
- X entry *t = list;
- X
- X (void) s; // "use" s so that CC won't complain
- X cout << "Available commands:\n\n";
- X cout << "quit\t";
- X
- X for(int max=1+int((t++)->name); t-list < max; t++)
- X cout << form("%s\t", t->name);
- X
- X cout.put('\n');
- X return 0;
- X }
- END_OF_testhelp.c
- if test 341 -ne `wc -c <testhelp.c`; then
- echo shar: \"testhelp.c\" unpacked with wrong size!
- fi
- # end of overwriting check
- fi
- echo shar: End of shell archive.
- exit 0
- --
- Reid Ellis, geaclib!rae@geac.uucp, rae@geaclib.uucp [if you're lucky]
-
-